// https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <deque>

using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
		vector<string> combinations;
        unordered_map<char, string> strMap = {
			{'2', "abc"},
			{'3', "def"},
			{'4', "ghi"},
			{'5', "jkl"},
			{'6', "mno"},
			{'7', "pqrs"},
			{'8', "tuv"},
			{'9', "wxyz"}
		};
		int height = digits.size();
		if(height == 0){
			return {};
		}
		string str = "23456789";
		for(int i = 0; i < height; i++){
			if(str.find(digits[i]) == string::npos){
				return {};
			}
		}
		int index = 0;
		vector<string> combines;
		string combine;
		// dfs(digits, index, height, combine, combines, strMap);
		bfs(digits, index, height, combines, strMap);
		return combines;
    }
	
	// 深度优先
	// digits 原始字符串
	// index 当前遍历的层高
	// height 总高度
	// combine 组合而成的字符串
	// combines 组合而成的字符串的集合
	// strMap 字符串map
	void dfs(string digits, int index, int height, string combine, vector<string> &combines, unordered_map<char, string> strMap){
		if(index == height){
			combines.push_back(combine);
			return;
		}
		char digit = digits[index];
		for(int i = 0; i < strMap.at(digit).size(); i++){
			combine.push_back(strMap.at(digit)[i]);
			dfs(digits, index+1, height, combine, combines, strMap);
			combine.pop_back();
		}
	}
	
	// 广度优先
	void bfs(string digits, int index, int height, vector<string> &combines, unordered_map<char, string> strMap) {
		if(index == height){
			return ;
		}
		char digit = digits[index];
		if(index == 0){
			for(int i = 0; i < strMap.at(digit).size(); i++){
				string tmp;
				tmp.push_back(strMap.at(digit)[i]);
				combines.push_back(tmp);
			}
		}else{
			vector<string> bfsVec;
			for(int i = 0; i < strMap.at(digit).size(); i++){
				char a1 = strMap.at(digit)[i];
				for(int j = 0; j < combines.size(); j++){
					string tmp = combines[j];
					tmp.push_back(a1);
					bfsVec.push_back(tmp);
				}
			}
			combines.assign(bfsVec.begin(), bfsVec.end());
		}
		bfs(digits, index+1, height, combines, strMap);
	}
};

int main(){
	Solution so;
	string input = "3344";
	vector<string> res = so.letterCombinations(input);
	for(auto v : res){
		cout << v << endl;
	}
	return 0;
}
